package edu.unice.simul.util.graphs;

/**
 * Cette classe modélise l'algorithme de Dijkstra
 * 
 * @author Romain Ciaccafava
 * 
 */
public class Dijkstra {
	private Graphe graphe;
	/**
	 * La file de priorité contient tous les sommets atteignables depuis le sommet
	 * de départ.
	 */
	private GrapheSommetsPriorityQueue priorityQ;

	public Dijkstra(Graphe g) {
		this.priorityQ = new GrapheSommetsPriorityQueue();
		this.graphe = g;
		this.graphe.getSommetDepart().setDistance(0.);
		this.priorityQ.add(this.graphe.getSommets());
	}

	/**
	 * Effectue l'algorithme de Dijkstra.
	 */
	public void calculer() {
		GrapheSommetsPriorityQueue queue = new GrapheSommetsPriorityQueue(priorityQ);

		while (!this.priorityQ.isEmpty()) {
			Sommet n = this.priorityQ.remove();
			for (Arc arc : n.getArcsSortants()) {
				Sommet sommetAdj = arc.getSommetDestination();
				double coutTemp = arc.getCout() + n.getDistance();
				if (coutTemp < sommetAdj.getDistance()) {
					sommetAdj.setDistance(coutTemp);
					this.priorityQ.updateDistanceSommet(sommetAdj);
				}
			}
		}

		this.priorityQ = queue;
	}
}
